W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Ulice w Bajtomieście tworzą prostopadłą siatkę - prowadzą ze wschodu na zachód lub z północy na południe. Ulice północ-południe są ponumerowane od 1 do w kolejności z zachodu na wschód. Podobnie ulice wschód-zachód są ponumerowane od 1 do w kolejności z południa na północ. Każda ulica północ-południe przecina każdą ulicę wschód-zachód i odwrotnie, każda ulica wschód-zachód przecina każdą północ-południe. Odległość między dwiema sąsiednimi ulicami północ-południe, a także sąsiednimi ulicami wschód-zachód jest równa jednemu kilometrowi.
W mieście znajduje się sklepów, a każdy sklep jest położony przy skrzyżowaniu ulic. Kupiec Bajtazar dostarcza towary do każdego z sklepów, przy czym część sklepów odwiedza kilka razy dziennie. Bajtazar postanowił wybudować magazyn, z którego dostarczałby towary do sklepów. Magazyn powinien być położony przy skrzyżowaniu ulic. Ciężarówka dostarczająca towary w trakcie jednego kursu może odwiedzić tylko jeden sklep - wyjeżdża z magazynu, dostarcza towar do sklepu i wraca do magazynu. Ciężarówka zawsze jedzie najkrótszą trasą z magazynu do sklepu i z powrotem. Odległość między punktami i jest równa
Napisz program, który:
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę sklepów w Bajtomieście.
Kolejne wierszy wejścia zawiera opisy sklepów. Wiersz -wszy zawiera trzy liczby całkowite , i (, ), oddzielone pojedynczymi odstępami. Ten opis oznacza, że -ty sklep jest położony na skrzyżowaniu -tej ulicy północ-południe i -tej ulicy wschód-zachód i ciężarówka codziennie dojeżdża do tego sklepu razy.
Pierwszy i jedyny wiersz wyjścia powinien zawierać dwie liczby całkowite oraz , oddzielone pojedynczym odstępem i opisujące położenie magazynu jako skrzyżowanie -tej ulicy północ-południe i -tej ulicy wschód-zachód. Jeżeli istnieje wiele poprawnych wyników, Twój program powinien wypisać dowolny z nich.
Dla danych wejściowych:
3 2 2 1 6 2 1 4 6 1
poprawną odpowiedzią jest:
4 4
Poniższy rysunek przedstawia sytuację z przykładowego wejścia. Ponumerowane punkty oznaczają odpowiednie sklepy. Punkt S oznacza optymalne położenie magazynu.
Autor zadania: Zbigniew Czech.